其他
据说这道题90%的人都搞错了
题目如下
package main
import (
"fmt"
)
func main() {
slice1 := make([]int, 0, 6)
slice2 := append(slice1, 1,2,3,4,5,6,7,8,9,10,11,12,13)
fmt.Println("slice1:", slice1)
fmt.Println("slice2", slice2, len(slice2), cap(slice2))
}
大家猜一下这题输出的 cap(slice2) 是多少?
~不
~要
~偷
~看
~答
~案
~:)
公布答案
slice1: []
slice2 [1 2 3 4 5 6 7 8 9 10 11 12 13] 13 14
解答
这是一个很常见的关于切片扩容的问题,相信大家也遇到过,首先我跟你们说一下切片的扩容机制:
当新切片需要的容量cap大于两倍扩容的容量,则直接按照新切片需要的容量扩容; 当原 slice 容量 < 1024 的时候,新 slice 容量变成原来的 2 倍; 当原 slice 容量 > 1024,进入一个循环,每次容量变成原来的1.25倍,直到大于期望容量。
很明显这个地方是属于第一种情况,我也给重点标记出来了。
因为slice2是在slice1的基础上进行append,所以可以认为原容量为6(定义slice1的时候设置的),然后一共需要存13个元素,就算扩容两倍到12还是不够,所以应该直接扩容到13......
那么问题就来了,这里为什么会输出14呢?
其实这里就是切片在扩容的时候会进行的一个内存对齐机制,多说无益,直接看源码(在\src\runtime\slice.go
):
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
oldLen := newLen - num
if raceenabled {
callerpc := getcallerpc()
racereadrangepc(oldPtr, uintptr(oldLen*int(et.Size_)), callerpc, abi.FuncPCABIInternal(growslice))
}
if msanenabled {
msanread(oldPtr, uintptr(oldLen*int(et.Size_)))
}
if asanenabled {
asanread(oldPtr, uintptr(oldLen*int(et.Size_)))
}
if newLen < 0 {
panic(errorString("growslice: len out of range"))
}
if et.Size_ == 0 {
// append should not create a slice with nil pointer but non-zero len.
// We assume that append doesn't need to preserve oldPtr in this case.
return slice{unsafe.Pointer(&zerobase), newLen, newLen}
}
newcap := nextslicecap(newLen, oldCap)
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.Size.
// For 1 we don't need any division/multiplication.
// For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
noscan := et.PtrBytes == 0
switch {
case et.Size_ == 1:
lenmem = uintptr(oldLen)
newlenmem = uintptr(newLen)
capmem = roundupsize(uintptr(newcap), noscan)
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.Size_ == goarch.PtrSize:
lenmem = uintptr(oldLen) * goarch.PtrSize
newlenmem = uintptr(newLen) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize)
case isPowerOfTwo(et.Size_):
var shift uintptr
if goarch.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
} else {
shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
}
lenmem = uintptr(oldLen) << shift
newlenmem = uintptr(newLen) << shift
capmem = roundupsize(uintptr(newcap)<<shift, noscan)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
capmem = uintptr(newcap) << shift
default:
lenmem = uintptr(oldLen) * et.Size_
newlenmem = uintptr(newLen) * et.Size_
capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
capmem = roundupsize(capmem, noscan)
newcap = int(capmem / et.Size_)
capmem = uintptr(newcap) * et.Size_
}
// The check of overflow in addition to capmem > maxAlloc is needed
// to prevent an overflow which can be used to trigger a segfault
// on 32bit architectures with this example program:
//
// type T [1<<27 + 1]int64
//
// var d T
// var s []T
//
// func main() {
// s = append(s, d, d, d, d)
// print(len(s), "\n")
// }
if overflow || capmem > maxAlloc {
panic(errorString("growslice: len out of range"))
}
var p unsafe.Pointer
if et.PtrBytes == 0 {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from oldLen to newLen.
// Only clear the part that will not be overwritten.
// The reflect_growslice() that calls growslice will manually clear
// the region not cleared here.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in oldPtr since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
//
// It's safe to pass a type to this function as an optimization because
// from and to only ever refer to memory representing whole values of
// type et. See the comment on bulkBarrierPreWrite.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes, et)
}
}
memmove(p, oldPtr, lenmem)
return slice{p, newLen, newcap}
}
------------------------------------------
func roundupsize(size uintptr, noscan bool) uintptr {
if size < _MaxSmallSize {
if size <= smallSizeMax-8 {
return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
} else {
return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
}
}
if size+_PageSize < size {
return size
}
return alignUp(size, _PageSize)
}
------------------------------------------
// divRoundUp returns ceil(n / a).
func divRoundUp(n, a uintptr) uintptr {
// a is generally a power of two. This will get inlined and
// the compiler will optimize the division.
return (n + a - 1) / a
}
这里简单解释一下:
首先执行roundupsize函数,64位系统是入参是newcap*ptrsize:13*8=104,32位系统是13×4。 执行内部的divRoundUp函数得到r1值为7 取size_to_class8下标为r1的值,得到r2,值为6 取class_to_size下标为r2的值,得到r3,值为112 r3转uintptr为r4,值一样 得到112,也就是变量capmem再除以ptrsize,即112/8=14
所以:新容量是14
拓展
这里额外提个问题,欢迎大家在评论区讨论一下:假如系统是32位的,这里的新容量应该是多少?
早日上岸!
我们搞了一个免费的面试真题共享群,互通有无,一起刷题进步。
没准能让你能刷到自己意向公司的最新面试题呢。
感兴趣的朋友们可以加我微信:wangzhongyang1993,备注:面试群。
点击下方文章,看看他们是怎么找到好工作的!
还有最新鲜的腾讯面经,不要错过哦!